#include "HuffmanTree.h"
#include "HTNSqList.h"
#include "HTNLinkQueue.h"
#include <iostream>
using namespace std;

HuffmanTree::HuffmanTree(int* a, int n)
{
	HTNSqList* list = new HTNSqList(a, n);
	int temp;
	for (int i = 0; i < list->length - 2; i = i + 2)
	{
		temp = list->data[i]->weight + list->data[i + 1]->weight;
		HTNode* p = new HTNode(temp);
		p->leftChild = list->data[i];
		p->rightChild = list->data[i + 1];
		list->data[i]->parent = p;
		list->data[i + 1]->parent = p;
		list->insertElement(p);
	}
	this->head = list->data[list->length - 1];
	delete list;
}

HuffmanTree::~HuffmanTree()
{
	deleteChildTree(this->head);
}

void HuffmanTree::displayTree()
{
	displayChildTree(this->head);
}

void HuffmanTree::breadthSearch()
{
	HTNLinkQueue* queue = new HTNLinkQueue();
	HTNode* temp;
	queue->enQueue(this->head);
	while (!queue->isEmpty())
	{
		temp = queue->deQueue();
		cout << temp->weight << " ";
		if (temp->leftChild != nullptr)
		{
			queue->enQueue(temp->leftChild);
		}
		if (temp->rightChild != nullptr)
		{
			queue->enQueue(temp->rightChild);
		}
	}
	cout << endl;
}

void deleteChildTree(HTNode* childHead)
{
	if (childHead == nullptr)
	{
		return;
	}
	deleteChildTree(childHead->leftChild);
	deleteChildTree(childHead->rightChild);
	delete childHead;
}

void displayChildTree(HTNode* childHead)
{
	if (childHead != nullptr)
	{
		cout << childHead->weight;
		if (childHead->leftChild != nullptr || childHead->rightChild != nullptr)
		{
			cout << "(";
			displayChildTree(childHead->leftChild);
			cout << ",";
			displayChildTree(childHead->rightChild);
			cout << ")";
		}
	}
}
